/*
 * @lc app=leetcode.cn id=39 lang=cpp
 *
 * [39] 组合总和
 */

#include <unordered_set>
#include <vector>

using std::vector;

// @lc code=start
class Solution
{
    void combinationSum_dfs(const vector<int> &candidates, int start, int target, vector<int> &choice, vector<vector<int>> &res)
    {
        if (target == 0) {
            res.push_back(choice);
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            int new_target = target - candidates[i];
            if (new_target >= 0) {
                choice.push_back(candidates[i]);
                /* 下一次开始选择的起始点，为当前的起始点，避免重复选择之前的 */
                combinationSum_dfs(candidates, i, new_target, choice, res);
                choice.pop_back();
            }
        }
    }

  public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        vector<int> choice;
        vector<vector<int>> res;
        combinationSum_dfs(candidates, 0, target, choice, res);
        return res;
    }
};
// @lc code=end
